package com.sudoku.solver;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

import com.badlogic.gdx.math.MathUtils;
import com.sudoku.board.Board;
import com.sudoku.board.Box;
import com.sudoku.board.CorrectBoard;
import com.sudoku.board.Tile;
import com.sudoku.observer.Event;
import com.sudoku.observer.Subject;
import com.sudoku.utility.Constants;
import com.sudoku.utility.Locator;
import com.sudoku.utility.Pair;

public class Solver extends Thread implements Constants {

	private int score;
	private Board board;
	private CorrectBoard correctBoard;
	private boolean finish;
	private boolean stuck;
	private HashSet<Integer> base = new HashSet<Integer>();
	private final ArrayList<Integer> BoxNumbers = new ArrayList<Integer>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9));
	private Queue<Pair<Tile, Character>> orderOfMoves;
	private ArrayList<Integer> indices;
	private Subject subject;

	// Strategies
	private HiddenTwin hiddenTwin;
	private UniquePencilCandidate uniquePencilCandidate;
	private SolePencilCandidate solePencilCandidate;
	private XWing xwing;

	public Solver(Board board, CorrectBoard correctBoard, Subject subject) {
		score = 0;
		finish = false;
		stuck = true;
		this.subject=subject;
		this.correctBoard=correctBoard;
		base.addAll(BoxNumbers);
		this.board = board;
		hiddenTwin = new HiddenTwin(this);
		uniquePencilCandidate = new UniquePencilCandidate(this);
		solePencilCandidate = new SolePencilCandidate(this);
		xwing = new XWing(this);
		orderOfMoves = new LinkedList<Pair<Tile, Character>>();
	}
	
	public void run(){
		generateStartTiles();
	}

	public boolean solve(DIFFICULTY difficulty) {
		finish = false;
		orderOfMoves.clear();
		pencilAllTiles();
		while (!finish) {
			if (verifyWin()) {
				finish = true;
				stuck = false;
			} else {
				stuck = true;

				// Only tile left in row or col
				// stuck = soleCandidate.solve(board);

				// Sole pencil candidates in tile
				stuck = solePencilCandidate.solve(board);

				// Unique penciled number in a row, col, or box
				if (stuck) {
					stuck = uniquePencilCandidate.solve(board);
				}

				if (!difficulty.equals(DIFFICULTY.EASY)) {
					// if still stuck, advanced strategy
					if (stuck) {
						// eliminate penciled numbers by finding 2 pairs of numbers
						stuck = hiddenTwin.solve(board);
					}
					if (!difficulty.equals(DIFFICULTY.HARD)) {
						// if still stuck, more advanced strategy
						if (stuck) {
							// eliminate penciled numbers by finding xwing pattern
							stuck = xwing.solve(board);
						}
					}
				}
				if (stuck) {
					finish = true;
				}
			}
		}
		return !stuck;
	}

	public void test() {
		stuck = xwing.solve(board);
	}

	private boolean verifyWin() {
		boolean solved = true;
		HashSet<Integer> base = new HashSet<Integer>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9));
		// check for duplicates in rows
		for (int i = 0; i < 9; i++) {
			base.removeAll(board.getBoardRow(i));
			if (base.size() != 0) {
				solved = false;
				break;
			}
			base.addAll(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9));
		}
		// check for duplicates in cols
		for (int i = 0; i < 9 && solved; i++) {
			base.removeAll(board.getBoardCol(i));
			if (base.size() != 0) {
				solved = false;
				break;
			}
			base.addAll(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9));
		}

		// check for duplicates in cols
		for (int i = 0; i < 9 && solved; i++) {
			base.removeAll(board.getData().get(i).getNumbers());
			if (base.size() != 0) {
				solved = false;
				break;
			}
			base.addAll(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9));
		}
		return solved;
	}

	/**
	 * Fill in all blank tiles with penciled numbers
	 */
	public void pencilAllTiles() {
		for (Box box : board.getData()) {
			for (Tile tile : box.getData()) {
				if (tile.isBlank()) {
					tile.clearPencilNumbers();
					pencilTile(tile, box);
				}
			}
		}
	}

	private void pencilTile(Tile tile, Box box) {
		// determine numbers in row
		base.removeAll(board.getBoardRow((int) ((ROWS_PER_BOX - 1 - box.getCoords().y) * BOXES_PER_BOARD + ROWS_PER_BOX - 1 - tile.getCoords().y)));
		// determine numbers in column
		base.removeAll(board.getBoardCol((int) ((box.getCoords().x * BOXES_PER_BOARD + tile.getCoords().x))));
		// determine numbers in box
		base.removeAll(box.getNumbers());
		tile.getPencilNumbers().addAll(base);
		refillBase();
	}

	public void refillBase() {
		base.addAll(BoxNumbers);
	}

	/*
	 * Update a tile with new data
	 */
	public void setNewTileData(Tile tile, char ch) {
		tile.setData(ch);
		orderOfMoves.add(new Pair<Tile, Character>(tile, tile.getData()));
		updatePencil(tile);
		refillBase();
	}

	/*
	 * Update the penciled-in numbers for everything this tile affects
	 */
	private void updatePencil(Tile tile) {
		final ArrayList<Tile> row = board
				.getTilesInRow((int) ((ROWS_PER_BOX - 1 - tile.getBox().getCoords().y) * BOXES_PER_BOARD + ROWS_PER_BOX - 1 - tile.getCoords().y));
		for (Tile t : row) {
			if (t.isBlank() && !tile.equals(t)) {
				t.clearPencilNumbers();
				pencilTile(t, t.getBox());
			}
		}
		final ArrayList<Tile> col = board.getTilesInCol((int) ((tile.getBox().getCoords().x * BOXES_PER_BOARD + tile.getCoords().x)));
		for (Tile t : col) {
			if (t.isBlank() && !tile.equals(t)) {
				t.clearPencilNumbers();
				pencilTile(t, t.getBox());
			}
		}
		Box box = tile.getBox();
		for (Tile t : box.getData()) {
			if (t.isBlank() && !tile.equals(t)) {
				t.clearPencilNumbers();
				pencilTile(t, box);
			}
		}
	}

	/**
	 * Generate a unique solution for the board. Create a stack of which tiles
	 * were removed
	 * 
	 * @param correctBoard
	 * @return the indices that were not picked
	 */
	public void generateStartTiles() {
		board.copyData(correctBoard);
		int counter = 0;
		indices = new ArrayList<Integer>();
		ArrayList<Integer> blankTiles = new ArrayList<Integer>();
		for (int i = 0; i < 81; i++) {
			indices.add(i, i);
		}

		//if we can't solve the board after 10 times, we are done 
		while (counter < 10) {
			int index = indices.remove(MathUtils.random(0, indices.size() - 1));
			Tile tile = board.getDataFromIndex(index);

			char data = tile.getData();
			tile.setBlank();

			// try to solve the board
			if (!solve(Locator.getDifficulty())) {
				// if we can't solve it, put tile data back into board and try another tile
				tile.setData(data);
				indices.add(index);

				counter++;
			} else {
				//we have successfully solved the board with this tile missing
				blankTiles.add(index);
				counter = 0;
				System.out.println("blanks: " + blankTiles.size() + " hints: " + orderOfMoves.size());
			}
			//reset blank indices to board
			for (int i = 0; i < blankTiles.size(); i++) {
				board.setBlankToIndex(blankTiles.get(i));
			}

		}
		solve(Locator.getDifficulty());
		subject.notify(Event.EVENT_SOLVED);
	}

	public HashSet<Integer> getBase() {
		return base;
	}

	public int getScore() {
		return score;
	}

	public Queue<Pair<Tile, Character>> getOrderOfMoves() {
		return orderOfMoves;
	}

	public ArrayList<Integer> getIndices() {
		return indices;
	}
}
